/**
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 *
 * 示例 2：
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 * 提示：
 * 1 <= nums.length <= 10
 * -10 <= nums[i] <= 10
 * nums 中的所有元素 互不相同
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 这一题我们对于每一个数我们有两个选择, 就是选和不选
 * 所以在递归的时候写两种方法就可以了
 * 时间复杂度 : O(n * 2 ^ n)
 * 空间复杂度 : O(2 ^ n)
 */

public class Main {

    // 全局变量
    List<List<Integer>> lists;
    List<Integer> list;
    int n;

    public List<List<Integer>> subsets(int[] nums) {

        // 初始化
        lists = new ArrayList<>();
        list = new ArrayList<>();
        n = nums.length;

        // 深搜
        dfs(nums, 0);

        return lists;
    }

    private void dfs (int[] nums, int k) {

        // 这里要是深搜完数组, 将结果添加进去结果集
        if (k == n) {
            lists.add(new ArrayList<>(list));
            return;
        }

        // 不选这个数
        dfs(nums, k + 1);

        // 选这个数
        list.add(nums[k]);

        dfs(nums, k + 1);

        // 恢复现场
        list.remove(list.size() - 1);
    }
}